public class 最小覆盖子串 {
    //https://leetcode.cn/problems/M1oyTv/description/
    //滑动窗口问题, 复习了一下
    public String minWindow(String ss, String tt) {
        char[] s = ss.toCharArray();
        char[] t = tt.toCharArray();
        //建立一下一个表,存储每个字符的个数
        int[] hash = new int[256];
        int n1 = s.length;
        int n2 = t.length;
        int count = 0;
        //如果t的长度比s的长度长, 就直接返回
        if(n2 > n1){
            return "";
        }
        //遍历一下t字符串, 如果有就减一下
        for(int i = 0;i < n2;i++){
            hash[t[i]]--;
        }
        //遍历一下有几个有效字符
        for(int i = 0;i < 256;i++){
            if(hash[i] < 0){
                count++;
            }
        }
        //双指针
        int left = 0;
        int index = -1;//第一个字符
        int len = 100001;//长度
        for(int right = 0;right < n1;right++){
            //进窗口, 如果已经达到0,就减减
            if(++hash[s[right]] == 0){
                count--;
            }
            //当有效字符全找到了, 左指针开始动,直到count不为0
            while(count == 0){
                //判断长度
                if(right - left + 1 < len){
                    index = left;
                    len = right - left + 1;
                }
                //判断有效字符
                if(--hash[s[left++]] < 0){
                    count++;
                }
            }
        }
        return index == -1 ? "":ss.substring(index,index + len);
    }
}
